package com.lun.swordtowardoffer2.c14;

public class MinCut {

	public int minCut(String str) {
		
		int len = str.length();
		boolean[][] isPal = new boolean[len][len];
		
		for(int i = 0 ; i < len; i++) {
			for(int j = 0; j <= i; j++) {
				char ch1 = str.charAt(j);//j是起始下标，这有点反直觉
				char ch2 = str.charAt(i);
				if(ch1 == ch2 && (i <= j + 1 ||isPal[j+1][i-1])) {
					isPal[j][i] = true;
				}
			}
		}
		
		int[] dp = new int[len];
		for(int i = 0 ; i < len; i++) {
			if(isPal[0][i]) {
				dp[i] = 0;
			}else {
				dp[i] = i;//最多
				for(int j = 0; j <= i; j++) {
					if(isPal[j][i]) {
						dp[i] = Math.min(dp[i], dp[j - 1] + 1);
					}
				}
			}
			
		}
				
		return dp[len - 1];
	}
	
	
}
